﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace InsertSort
{
	class Program
	{
		/// <summary>
		/// 直接插入排序时间复杂度：O(N^2)
		/// </summary>
		/// <param name="args"></param>
		static void Main(string[] args)
		{
			List<int> list=new List<int>(){20,60,10,40,30,70};
			Console.WriteLine("排序前："+string.Join(",",list));
			InsertSort(list);
			Console.WriteLine("直接选择排序后：" + string.Join(",", list));
			Console.ReadLine();
		}

		/// <summary>
		/// 直接插入排序
		/// </summary>
		/// <param name="list"></param>
		static void InsertSort(List<int> list )
		{
			//无序序列
			for (int i = 1; i < list.Count; i++)
			{
				var temp = list[i];
				int j;
				//有序序列
				for (j = i-1;j >= 0  &&  temp < list[j]; j--)
				{
					list[j + 1] = list[j];
				}
				list[j + 1] = temp;
			}
		}
	}
}
